home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / man / node_matrix.tex < prev    next >
Encoding:
Text File  |  1994-08-05  |  2.3 KB  |  63 lines
  1. \bigskip
  2. \bigskip
  3. {\magonebf 5.8 Two dimensional node arrays  (node\_matrix)}
  4.  
  5. \decl node\_matrix E 
  6.  
  7. {\bf 1. Definition}
  8.  
  9. An instance $M$ of the parameterized data type \name\ is 
  10. a partial mapping from the set of node pairs $V\times V$
  11. of a graph to the set of variables of data type $E$, called the element type 
  12. of $M$. The domain $I$ of $M$ is called the index set of $M$. $M$ is said to 
  13. be valid for all node pairs in $I$. A node matrix can also be viewed as a 
  14. node array with element type $node\_array(E)$ ($node\_array(node\_array(E))$). 
  15.  
  16. \bigskip
  17. {\bf 2. Creation}
  18.  
  19.  
  20. a) \create M {}
  21.  
  22. b) \create M (G)
  23.  
  24. c) \create M (G,x)
  25.  
  26. creates an instance $M$ of type \name. Variant a) initializes the index set 
  27. of $M$ to the empty set, Variants b) and c) initialize the index set of $A$ 
  28. to be the set of all node pairs of graph $G$, i.e., $M$ is made valid for all 
  29. pairs in $V \times V$ where $V$ is the set of nodes currently contained in $G$. 
  30. Variant c) in addition initializes  $M(v,w)$ with $x$ for all nodes $v,w \in V$.
  31.  
  32.  
  33. \bigskip
  34. {\bf 3. Operations }
  35. \medskip
  36. \+\op void  init {graph\ G}         
  37.                              {sets the index set of $M$ to $V\times V$, where }
  38. \+\nop                       {$V$ is the set of all nodes of $G$ }
  39. \smallskip
  40. \+\op void  init {graph\ G,\ E\ x}    
  41.                             {sets the index set of $M$ to $V\times V$, where }
  42. \+\nop                      {$V$ is the set of all nodes of $G$ and initializes}
  43. \+\nop                      {$M(v,w)$ to $x$ for all $v,w \in V$.}
  44. \smallskip
  45. \+\opf E\&  {node\ v,\ node\ w}
  46.                             {returns the variable $M(v,w)$.}
  47. \+\nop                      {\precond $M$ must be valid for $v$ and $w$.}
  48. \smallskip
  49. \+&$node\_array(E)\&$ $M[v]$ &&returns the node\_array  $M(v).$\cr
  50.  
  51. \bigskip
  52. {\bf 4. Implementation}
  53.  
  54. Node matrices for a graph $G$ are implemented by vectors of node arrays and an 
  55. internal numbering of the nodes of $G$. The access operation 
  56. takes constant time, the init operation takes time $O(n^2)$, where $n$ is the 
  57. number of nodes currently contained in $G$. The space requirement is $O(n^2)$.
  58. Note that a node matrix is only valid for the nodes contained in $G$ at the 
  59. moment of the matrix declaration or initialization ($init$). Access operations 
  60. for later added nodes are not allowed.
  61.  
  62.  
  63.